{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Validate Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ，判断其是否是一个有效的二叉搜索树。</p>\n",
    "\n",
    "<p><strong>有效</strong> 二叉搜索树定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的左子树只包含<strong> 小于 </strong>当前节点的数。</li>\n",
    "\t<li>节点的右子树只包含 <strong>大于</strong> 当前节点的数。</li>\n",
    "\t<li>所有左子树和右子树自身必须也是二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg\" style=\"width: 302px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg\" style=\"width: 422px; height: 292px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,1,4,null,null,3,6]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>根节点的值是 5 ，但是右子节点的值是 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目范围在<code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= Node.val &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [validate-binary-search-tree](https://leetcode.cn/problems/validate-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [validate-binary-search-tree](https://leetcode.cn/problems/validate-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]', '[5,1,4,null,null,3,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        def validBST(root, minv, maxv):\n",
    "            isLeftBalance = True\n",
    "            isRightBalance = True\n",
    "            if root.left:\n",
    "                if minv < root.left.val < root.val:\n",
    "                    isLeftBalance = validBST(root.left, min(minv, root.left.val), root.val)\n",
    "                else:\n",
    "                    print(root.left.val, root.val, minv)\n",
    "                    return False\n",
    "            if root.right:\n",
    "                if maxv > root.right.val > root.val:\n",
    "                    isRightBalance = validBST(root.right, root.val, max(maxv, root.right.val))\n",
    "                else:\n",
    "                    print(root.right.val, root.val, maxv)\n",
    "                    return False\n",
    "            return isLeftBalance and isRightBalance\n",
    "        return validBST(root, 0-pow(2,31)-1, pow(2,31)+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: 'TreeNode') -> 'bool':\n",
    "        \n",
    "        # recursive\n",
    "#         def validBST(root, low, high):\n",
    "#             if not root:\n",
    "#                 return True\n",
    "#             elif root.val >= high or root.val <= low:\n",
    "#                 return False\n",
    "#             else:\n",
    "#                 return validBST(root.left, low, root.val) and validBST(root.right, root.val, high)\n",
    "            \n",
    "#         return validBST(root, float('-inf'), float('inf'))\n",
    "\n",
    "        # iterative in-order sort\n",
    "        stack, node, val = [], root, float('-inf')\n",
    "        while stack or node:\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                \n",
    "                if node.val <= val:\n",
    "                    return False\n",
    "                val = node.val\n",
    "                \n",
    "                node = node.right\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: 'TreeNode') -> 'bool':\n",
    "        \n",
    "        def validBST(root, low, high):\n",
    "            if not root:\n",
    "                return True\n",
    "            elif root.val >= high or root.val <= low:\n",
    "                return False\n",
    "            else:\n",
    "                return validBST(root.left, low, root.val) and validBST(root.right, root.val, high)\n",
    "            \n",
    "        return validBST(root, float('-inf'), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.checkBST(root, None, None)\n",
    "    \n",
    "    def checkBST(self, node, lowerBound, upperBound):\n",
    "        if node == None:\n",
    "            return True\n",
    "        \n",
    "        if not ((lowerBound == None or node.val > lowerBound) and \n",
    "                (upperBound == None or node.val < upperBound)):\n",
    "            return False\n",
    "        \n",
    "        left = self.checkBST(node.left, lowerBound, node.val)\n",
    "        right = self.checkBST(node.right, node.val, upperBound)\n",
    "\n",
    "        return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        self.helper(root,res)\n",
    "        \n",
    "        for i in range(1,len(res)):\n",
    "            if res[i]<=res[i-1]:\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "    \n",
    "       \n",
    "    \n",
    "    def helper(self,root,res):\n",
    "        if root is None:\n",
    "            return res\n",
    "        \n",
    "        self.helper(root.left,res)\n",
    "        res.append(root.val)\n",
    "        self.helper(root.right,res)\n",
    "        \n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def findMax(root):\n",
    "    if root.left == None and root.right == None:\n",
    "        return root.val\n",
    "    t1 = -2147483648\n",
    "    t2 = -2147483648\n",
    "    if root.left != None:\n",
    "        t1 = findMax(root.left)\n",
    "    if root.right != None:\n",
    "        t2 = findMax(root.right)\n",
    "    return max(t1, t2, root.val)\n",
    "\n",
    "def findMin(root):\n",
    "    if root.left == None and root.right == None:\n",
    "        return root.val\n",
    "    t1 = 2147483647\n",
    "    t2 = 2147483647\n",
    "    if root.left != None:\n",
    "        t1 = findMin(root.left)\n",
    "    if root.right != None:\n",
    "        t2 = findMin(root.right)\n",
    "    return min(t1, t2, root.val)\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: 'TreeNode') -> 'bool':\n",
    "        if root == None:\n",
    "            return True\n",
    "        if root.left != None and findMax(root.left) >= root.val:\n",
    "            return False\n",
    "        if root.right != None and findMin(root.right) <= root.val:\n",
    "            return False\n",
    "        return self.isValidBST(root.left) and self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        result=[]\n",
    "        self.inorder(root,result)\n",
    "        for i in range(1,len(result)):\n",
    "            if result[i]<=result[i-1]:\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "    def inorder(self,root,result):\n",
    "        if root  is None:\n",
    "            return True\n",
    "        self.inorder(root.left,result)\n",
    "        result.append(root.val)\n",
    "        self.inorder(root.right,result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root: return True\n",
    "        t = list(self.traversal(root))\n",
    "        return t == sorted(list(set(t)))\n",
    "    \n",
    "    def traversal(self, root):\n",
    "        if root:\n",
    "            yield from self.traversal(root.left)\n",
    "            yield root.val\n",
    "            yield from self.traversal(root.right)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def istree(root):\n",
    "            if root is None:\n",
    "                return []\n",
    "            res = []\n",
    "            res += istree(root.left)\n",
    "            res.append(root.val)\n",
    "            res += istree(root.right)\n",
    "            return res\n",
    "        res = istree(root)\n",
    "        if res != sorted(list(set(res))):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def midOrderSearch(self, node: TreeNode) -> List[int]:\n",
    "        \"\"\"\n",
    "        中序遍历\n",
    "        \"\"\"\n",
    "        if not node:\n",
    "            return []\n",
    "        return self.midOrderSearch(node.left) + [node.val] + self.midOrderSearch(node.right)\n",
    "    \n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        ret = self.midOrderSearch(root)\n",
    "        return ret == sorted(list(set(ret)))\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import sys\n",
    "class Solution:\n",
    "    last_val = -sys.float_info.max\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return True\n",
    "        left = self.isValidBST(root.left)\n",
    "        right = self.isValidBST(root.right)\n",
    "        \n",
    "        if root.left!=None:\n",
    "            if not self.left_isvalid(root.left,root.val):\n",
    "                return False\n",
    "        if root.right!=None:\n",
    "            if not self.right_isvalid(root.right,root.val):\n",
    "                return False\n",
    "        return left and right\n",
    "    def left_isvalid(self,node,val):\n",
    "        if node == None:\n",
    "            return True\n",
    "        if node.val>=val:\n",
    "            return False\n",
    "        if self.left_isvalid(node.left,val) and self.left_isvalid(node.right,val):\n",
    "            return True\n",
    "    def right_isvalid(self,node,val):\n",
    "        if node == None:\n",
    "            return True\n",
    "        if node.val<=val:\n",
    "            return False\n",
    "        if self.right_isvalid(node.left,val) and self.right_isvalid(node.right,val):\n",
    "            return True    \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        # 动态改变每一个深度的区间 并以此来判断二叉搜索数是否有效\n",
    "        # 区间数组\n",
    "        M = float('inf')\n",
    "        c = [-M, M]\n",
    "        def dfs_(root, c):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val >= c[1] or root.val <= c[0]:\n",
    "                return False\n",
    "            c_left = [c[0], root.val]\n",
    "            c_right = [root.val, c[1]]\n",
    "            return dfs_(root.left, c_left) and dfs_(root.right, c_right)\n",
    "        return dfs_(root, c)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "def is_legal(root,lval,rval):\n",
    "    if root is None:\n",
    "        return True\n",
    "    else:\n",
    "        return root.val>lval and root.val<rval and is_legal(root.left,lval,root.val) and is_legal(root.right,root.val,rval)\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return is_legal(root,-1*pow(2,32),pow(2,32))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        stack = [root]\n",
    "        ans = []\n",
    "        while stack:\n",
    "            temp = stack[-1]\n",
    "            if temp.left is not None:\n",
    "                stack.append(temp.left)\n",
    "                temp.left = None\n",
    "            elif temp.right is not None:\n",
    "                ans.append(temp.val)\n",
    "                stack.pop()\n",
    "                stack.append(temp.right)\n",
    "                temp.right = None\n",
    "            else:\n",
    "                ans.append(temp.val)\n",
    "                stack.pop()\n",
    "        for i in range(len(ans) - 1):\n",
    "            if ans[i] >= ans[i + 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# 错误的解答\n",
    "# class Solution:\n",
    "#     def isValidBST(self, root: TreeNode) -> bool:\n",
    "#         if not root:  # 空节点\n",
    "#             return True\n",
    "#         is_valid = True\n",
    "#         if root.left:\n",
    "#             is_valid = is_valid and root.val > root.left.val # 应该要判断整个左子树是否都小于根节点\n",
    "#         if root.right:\n",
    "#             is_valid = is_valid and root.val < root.right.val\n",
    "#         if not is_valid:\n",
    "#             return False\n",
    "#         else:\n",
    "#             return self.isValidBST(root.left) and self.isValidBST(root.right)\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        inorder_result = self.inorder(root)\n",
    "        n = len(inorder_result)\n",
    "        for i in range(n):\n",
    "            if i+1 < n and inorder_result[i] >= inorder_result[i+1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def inorder(self, root: TreeNode):  # 中序遍历\n",
    "        # 非递归\n",
    "        stack = []\n",
    "        result = []\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                p = stack.pop()\n",
    "                result.append(p.val)\n",
    "                root = p.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def recursion(root, lower, upper):\n",
    "            if root == None:\n",
    "                return True\n",
    "\n",
    "            val = root.val\n",
    "\n",
    "            if lower != None and val <= lower:\n",
    "                return False\n",
    "\n",
    "            if upper != None and val >= upper:\n",
    "                return False\n",
    "\n",
    "            if not recursion(root.right, val, upper):\n",
    "                return False\n",
    "            \n",
    "            if not recursion(root.left, lower, val):\n",
    "                return False\n",
    "            \n",
    "            return True\n",
    "\n",
    "        return recursion(root, None, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(minVal,maxVal,curRoot):\n",
    "            if minVal<curRoot.val<maxVal:\n",
    "                leftValid=True\n",
    "                rightValid=True\n",
    "                if curRoot.left:\n",
    "                    leftValid=helper(minVal,min(curRoot.val,maxVal),curRoot.left)\n",
    "                if curRoot.right:\n",
    "                    rightValid=helper(max(minVal,curRoot.val),maxVal,curRoot.right)\n",
    "                return leftValid and rightValid\n",
    "            else:\n",
    "                return False\n",
    "        if root is None:\n",
    "            return False\n",
    "        return helper(-2**31-1,2**31,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def isValidBSTHelper(self, root: TreeNode, lower: int, upper: int):\n",
    "        \n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        if not lower < root.val < upper:\n",
    "            return False\n",
    "        return self.isValidBSTHelper(root.left, lower, root.val) and self.isValidBSTHelper(root.right, root.val, upper)\n",
    "        \n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return self.isValidBSTHelper(root, float('-inf'), float('inf'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isValidBST(self, root: TreeNode) -> bool:  # 非递归暴力解法，采用BFS遍历，对每个节点进行判断\n",
    "#         if root is None:\n",
    "#             return True\n",
    "#         queue = [root]\n",
    "#         while queue:\n",
    "#             curr = queue.pop(0)\n",
    "#             if curr.left:\n",
    "#                 queue.append(curr.left)\n",
    "#                 tmp_node = curr.left\n",
    "#                 while tmp_node:\n",
    "#                     if tmp_node.val >= curr.val:\n",
    "#                         return False\n",
    "#                     tmp_node = tmp_node.right\n",
    "#             if curr.right:\n",
    "#                 queue.append(curr.right)\n",
    "#                 tmp_node = curr.right\n",
    "#                 while tmp_node:\n",
    "#                     if tmp_node.val <= curr.val:\n",
    "#                         return False\n",
    "#                     tmp_node = tmp_node.left\n",
    "#         return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = -float(\"inf\")  # 初始化前一个节点的值为负无穷大\n",
    "        \n",
    "    def isValidBST(self, root: TreeNode) -> bool:  # 递归解法：主要利用了中序遍历二叉搜索树会产生递增序列\n",
    "        if root is None:  # 如果当前节点为空，则返回True\n",
    "            return True\n",
    "        if not self.isValidBST(root.left):  # 否则，判断左子树，如果左子树不合法，则返回False\n",
    "            return False\n",
    "        if root.val <= self.pre:  # 左子树判断结束，判断当前节点与中序遍历前一个节点的值，如果当前节点的值不大于前一个节点的值，则返回False\n",
    "            return False\n",
    "        self.pre = root.val  # 否则，把当前节点的值作为前一个节点的值，用于后续的中序遍历判断\n",
    "\n",
    "        return self.isValidBST(root.right)  # 判断某个子树的右子树\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = -float(\"inf\")\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        if not self.isValidBST(root.left):\n",
    "            return False\n",
    "        if root.val <= self.pre:\n",
    "            return False\n",
    "        self.pre = root.val\n",
    "\n",
    "        return self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def isValid(T):\n",
    "            if T == None:\n",
    "                return [float('inf'), float('-inf'), 1]\n",
    "\n",
    "            isBST = 1\n",
    "\n",
    "            values1 = isValid(T.left)\n",
    "            if T.val <= values1[1]:\n",
    "                isBST = 0\n",
    "\n",
    "            values2 = isValid(T.right)\n",
    "            if T.val >= values2[0]:\n",
    "                isBST = 0\n",
    "            isBST = isBST * values2[2] * values1[2]\n",
    "            \n",
    "            maxVal = max([T.val, values1[1], values2[1]])\n",
    "            minVal = min([T.val, values1[0], values2[0]])\n",
    "\n",
    "            return [minVal, maxVal, isBST]\n",
    "        if root == None:\n",
    "            return True\n",
    "        return isValid(root)[2] == 1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def valid(node, left=float('-inf'), right = float('inf')):\n",
    "            if not node:\n",
    "                return True\n",
    "            val = node.val\n",
    "            if val <= left or val >= right:\n",
    "                return False\n",
    "            return valid(node.left, left, val) and valid(node.right, val, right)\n",
    "        \n",
    "        return valid(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        # 循环条件为什么这么定？\n",
    "        # 一开始有cur 无stack 最后 有stack 无cur\n",
    "        while cur or stack:\n",
    "            if cur: # 指针来访问节点，访问到最底层\n",
    "                stack.append(cur)\n",
    "                cur = cur.left# 左\n",
    "            else: # 逐一处理节点\n",
    "                cur = stack.pop()\n",
    "\n",
    "                if pre and cur.val <= pre.val: # 比较当前节点和前节点的值的大小\n",
    "                    return False\n",
    "                pre = cur\n",
    "                cur = cur.right# 右\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        stack = []  # 不能提前将root结点加入stack中\n",
    "        pre = None\n",
    "        cur = root\n",
    "        while cur or stack:\n",
    "            # 先迭代访问最底层的左子树结点\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            # 到达最左结点后处理栈顶结点\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre and cur.val <= pre.val: # 比较当前节点和前节点的值的大小\n",
    "                    return False\n",
    "                # 取栈顶元素右结点\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 中序遍历\n",
    "\n",
    "        stack, inorder = [], float('-inf')\n",
    "\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if root.val <= inorder:\n",
    "                return False\n",
    "            inorder = root.val\n",
    "            root = root.right\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode],left=-inf,right=inf) -> bool:\n",
    "        #前序遍历验证二叉搜索树 根-左-右   root [-inf,inf] left[-inf,root.val] right[root.val,inf] 同时满足 left<root.val<right\n",
    "        if root is None:\n",
    "            return True\n",
    "        x=root.val\n",
    "        return left<x<right and self.isValidBST(root.left,left,x) and self.isValidBST(root.right,x,right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        def helper(node, lower=-inf, upper=inf): \n",
    "        # 第一次判断根节点的值是否符合条件时，由于根节点可以取任意值，所以上下界为正负无穷\n",
    "            if not node:\n",
    "                return True\n",
    "\n",
    "            # 先把所有False的情况写出来，最后再return True\n",
    "            if node.val <= lower or node.val >= upper:\n",
    "                return False\n",
    "            if not helper(node.left, lower, node.val):\n",
    "                return False\n",
    "            if not helper(node.right, node.val, upper):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        return helper(root)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.pre = None\n",
    "        def inorder(node):\n",
    "            if(not node):\n",
    "                return True\n",
    "            left = inorder(node.left)\n",
    "            if(left):\n",
    "                if(not self.pre):\n",
    "                    self.pre = node\n",
    "                    return inorder(node.right)\n",
    "                elif(self.pre.val < node.val):\n",
    "                    self.pre = node\n",
    "                    return inorder(node.right)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        return inorder(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        stack = []\n",
    "        inorder = - 2**(31) - 1\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if root.val <= inorder:\n",
    "                return False\n",
    "            inorder = root.val\n",
    "            root = root.right\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.left = -2**32\n",
    "        self.right = 2**32\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        def help(root,min_left,max_right):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.left:\n",
    "                if root.val <= root.left.val:\n",
    "                    return False\n",
    "            if root.right:\n",
    "                if root.val >= root.right.val:\n",
    "                    return False\n",
    "            if root.val <= min_left:\n",
    "                    return False\n",
    "            if root.val >= max_right:\n",
    "                    return False\n",
    "            return help(root.left,min_left,root.val) and help(root.right,root.val,max_right)\n",
    "        return help(root,self.left,self.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        def isBST(root, minv, maxv):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val >= maxv or root.val <= minv:\n",
    "                return False\n",
    "            return isBST(root.left, minv, root.val) and isBST(root.right, root.val, maxv)\n",
    "        return isBST(root, -float('inf'), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        def helper(node, minval, maxval):\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val>=maxval or node.val<=minval:\n",
    "                return False\n",
    "            left = helper(node.left, minval, node.val)\n",
    "            right = helper(node.right, node.val, maxval)\n",
    "            return left and right\n",
    "        return helper(root, float('-inf'), float('inf'))\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#  中序遍历就是递增序列了，利用双指针，避免第一个节点值就是float最小值\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = TreeNode(val=None)\n",
    "\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root == None:\n",
    "            return True\n",
    "\n",
    "        left_bool = self.isValidBST(root.left)\n",
    "\n",
    "        if self.pre.val != None and root.val <= self.pre.val:\n",
    "            return False\n",
    "        self.pre = root\n",
    "\n",
    "        right_bool = self.isValidBST(root.right)\n",
    "\n",
    "        return left_bool&right_bool\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
